package com.leetcode.search;

import java.util.*;

/**
 * leetcode 841 钥匙和房间
 */
public class Solution841 {
    public boolean canVisitAllRooms(List<List<Integer>> rooms) {
        if (rooms == null) {
            return false;
        }

        Set<Integer> visited = new HashSet<>(Arrays.asList(0));
        return canVisitAllRooms(rooms, 0, visited);
    }

    private boolean canVisitAllRooms(List<List<Integer>> rooms, int index, Set<Integer> visited) {
        if (visited.size() == rooms.size()) {
            return true;
        }

        // 取出所有可以访问的路径
        for (Integer key : rooms.get(index)) {
            if (!visited.contains(key)) {
                visited.add(key);
                if (canVisitAllRooms(rooms, key, visited)) {
                    return true;
                }
            }
        }
        return false;
    }

    public static void main(String[] args) {
        Solution841 solution841 = new Solution841();
        List<List<Integer>> rooms = new ArrayList<>();
        ArrayList<Integer> room1 = new ArrayList<>(Arrays.asList(2, 3));
        ArrayList<Integer> room2= new ArrayList<>(Arrays.asList());
        ArrayList<Integer> room3 = new ArrayList<>(Arrays.asList(2));
        ArrayList<Integer> room4 = new ArrayList<>(Arrays.asList(1, 3));
        rooms.add(room1);
        rooms.add(room2);
        rooms.add(room3);
        rooms.add(room4);
        System.out.println(solution841.canVisitAllRooms(rooms));
    }
}
